/*
7.24
time:20201208 17:11 PM
key:1.从p开始的随机方向用随机数决定
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
#include <iostream>
#include <cstdlib> 
#include <ctime> 
class Node
{
public:
	int key;
	Node* lchild;
	Node* rchild;

	Node()
	{
		key = -1;
		lchild = NULL;
		rchild = NULL;
	}
};

Node* search(Node* head, Node* p, int key)
{
	//随机奇数偶数
	unsigned seed;
	seed = time(0);
	srand(seed);
	
	//从head开始右遍历找到p
	Node* p1 = head;
	while (1)
	{
		if (p1 == p)
		{
			break;
		}
		p1 = p1->rchild;
	}
	//从p开始随机选择左或右遍历找到key
	p1 = p;
	if (rand() % 2) 
	{
		cout << "从p开始选择右遍历找到key" <<  endl;
		while (1)
		{
			if (p1->key == key)
			{
				return p1;
				break;
			}
			p1 = p1->rchild;
		}
	}
	else
	{
		cout << "从p开始选择左遍历找到key" << endl;
		while (1)
		{
			if (p1->key == key)
			{
				return p1;
				break;
			}
			p1 = p1->lchild;
		}
	}
}
int main()
{
	int range_array[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };//有序数组
	Node* head = new Node;
	int i, j;
	int n = 10;
	Node* p = new Node;
	p = head;
	//构建双向链表
	for (i = 0; i < n; i++)
	{
		p->key = range_array[i];
		if (i == n - 1)
		{
			//尾右指头
			p->rchild = head;
			//头左指尾
			head->lchild = p;
		}
		else
		{
			//右指针的左指针指回自己
			p->rchild = new Node;
			p->rchild->lchild = p;
			p = p->rchild;
		}
	
		
	}
	//右遍历
	p = head;
	while (0)
	{
		cout << p->key << "";
		p = p->rchild;
	}
	//左遍历
	p = head;
	while (0)
	{
		cout << p->key << "";
		p = p->lchild;
	}
	//search
	p = head;
	int key;
	cin >> key;
	p=search(head, p, key);
	cout << "函数运行完p指针数据是" << p->key << endl;
}




